package algorithm.search.binary.cyclic;

import algorithm.sort.array.SortQuick;

import java.util.Random;

/**
 * @program: beauty_of_data_structure_and_algotithm
 * @description: a cyclic sorted int array, and find one value.
 * @author: Keyu Li
 * @create: 2021-09-02 16:10
 **/

public class SearchCyclicArray {
    final static int ARRAY_LENGTH = 60;
    final static int INT_RANGE = ARRAY_LENGTH * 3;
    final static int ARRAY_NUM = 15;
    static int[][] arr = new int[ARRAY_NUM][ARRAY_LENGTH];
    static int[] searchTarget = new int[ARRAY_NUM];
    static int[] cyclicPoint = new int[ARRAY_NUM];

    public static void main(String[] args) {
        normalTest();
        // 测试 只有两个值：1，2 的情况。
//        sameValueTest();
    }


    private static void normalTest() {
        for (int i = 0; i < ARRAY_NUM; i++) {
            searchTarget[i] = createRandomSortedArray(arr[i]);
            arr[i] = cyclicArray(arr[i]);
            // 测试 只有两个值的情况。
            showArray(arr[i]);

            cyclicPoint[i] = getCyclicPoint(arr[i]);
            System.out.println("target: " + searchTarget[i] + " cyclic point: " + cyclicPoint[i]
                    + " index: " + getTargetIndex(arr[i], searchTarget[i], cyclicPoint[i]));
        }
    }

    // 测试 只有两个值的情况。
    private static void sameValueTest() {
        for (int i = 0; i < ARRAY_NUM; i++) {
            for (int j = 0; j < ARRAY_LENGTH; j++) {
                arr[i][j] = 2;
            }
            for (int j = 0; j < i+1; j++) {
                arr[i][30+j] = 1;
            }
            showArray(arr[i]);

            cyclicPoint[i] = getCyclicPoint(arr[i]);
            System.out.println("target: " + 1 + " cyclic point: " + cyclicPoint[i]
                    + " index: " + getTargetIndex(arr[i], 1, cyclicPoint[i]));
        }
    }


    private static int getTargetIndex(int[] arr, int target, int offSet) {
        int low = offSet;
        int high = arr.length - 1 + offSet;
        int mid, realMid;
        while (low <= high) {
            mid = (low + high) >> 1;
            realMid = mid <= arr.length - 1 ? mid : mid + 1 - arr.length;
            if (arr[realMid] == target)
                return realMid;
            else if (arr[realMid] > target)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }

    private static int getCyclicPoint(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        int mid;
        int cyclicPoint = 0;

        while (low <= high) {
            mid = (low + high) >> 1;
//            System.out.println(low + ", " + high + ", " + mid);
            // 此时 low-high 为递增数组，low即为转折点
            if (arr[low] < arr[high])
                return low;
            if (mid != 0 && arr[mid - 1] > arr[mid])
                return mid;
            // low high 数据相等，必须使其中一点跳出此区间，否则无法缺点 mid 点所在位置。
            if (arr[low] == arr[high]) {
                low++;
                continue;
            }
            if (arr[mid] >= arr[low])
                low = mid + 1;
            else
                high = mid - 1;
        }
        return cyclicPoint;
    }


    private static int[] cyclicArray(int[] arrRd) {
        Random rd = new Random();
        int[] arrResult = new int[ARRAY_LENGTH];
        // make cyclic
        int point = rd.nextInt(ARRAY_LENGTH / 2) + ARRAY_LENGTH / 4;
        // 测试 循环点为第0位、第1位、倒数第2位的情况。
//        point = 0;
//        point = 1;
//        point = arrRd.length - 1;

        int index = 0;
        for (int i = point; i < ARRAY_LENGTH; i++, index++) {
            arrResult[index] = arrRd[i];
        }
        for (int i = 0; i < point; i++, index++) {
            arrResult[index] = arrRd[i];
        }
        return arrResult;
    }


    private static int createRandomSortedArray(int[] arrRd) {
        Random rd = new Random();

        for (int i = 0; i < ARRAY_LENGTH; i++) {
            arrRd[i] = rd.nextInt(INT_RANGE) + 1;
        }
        int returnRanValue = arrRd[rd.nextInt(ARRAY_LENGTH)];
        // sort
        SortQuick sq = new SortQuick();
        sq.sort(arrRd);
        //return random value.
        return returnRanValue;
    }

    private static void showArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
            if ((i + 1) % 10 == 0)
                System.out.print(", ");
        }
        System.out.println();
    }


}
